// AdditionalReviewProblems.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <array>
#include <string>
#include <vector>
#include <algorithm>
#include <iterator>

using namespace std;

void testIntegerToPhrase()
{
    //17.7 Given any integer, print an English phrase that describes the integer (e.g., "One
    //Thousand, Two Hundred Thirty Four").
}

void searchLargestSum()
{
    //17.8 You are given an array of integers (both positive and negative). Find the contiguous
    //sequence with the largest sum. Return the sum.
}

bool canBuildWord(string const& str, vector<string> const& dictionary, bool includeSelf)
{
    if (str.empty())
    {
        return true;
    }

    int length = (includeSelf) ? str.length() : str.length() - 1; 
    for (int i = 1; i <= length; i++)
    {
        auto sub = str.substr(0, i);
        if ( find(dictionary.begin(), dictionary.end(), sub) != dictionary.end() && 
            canBuildWord(str.substr(i), dictionary, true))
        {
            return true;
        }
    }

    return false;
}

string getLongestWord(vector<string> const& data)
{
    auto local = data;
    sort(local.begin(), local.end(), [](string const& left, string const& right)
    {
        return right.length() < left.length();
    });

    string ret;
    for(int i = 0; i < local.size(); i++)
    {
        if (canBuildWord(local[i], data, false))
        {
            return local[i];
        }
    }
    return "";
}

void testGetLongestWord()
{
    //18.7 Given a list of words, write a program to find the longest word made of other words
    //in the list.
    string data[] = {"abc", "abcdef", "def", "abcdefgh", "gh"};
    copy(begin(data), end(data), ostream_iterator<string>(cout, ", "));
    auto ret = getLongestWord(vector<string>(begin(data), end(data)));
    cout << ret.c_str() << endl;
}

class MedianValue
{
public:
    void add(int value)
    {
        if (_miniHeap.empty() && _maxHeap.empty())
        {
            _maxHeap.push_back(value);
            return;
        }

        if (_miniHeap.size() == _maxHeap.size())
        {
            //always keep the size of _maxHeap lager than the size of _miniHeap.
            _maxHeap.push_back(value);
            push_heap(_maxHeap.begin(), _maxHeap.end(), [](int left, int right){ return left >= right; });
        }
        else
        {
            if (value > _maxHeap.front())
            {
                _miniHeap.push_back(_maxHeap.front());
                push_heap(_miniHeap.begin(), _miniHeap.end());

                pop_heap(_maxHeap.begin(), _maxHeap.end());
                _maxHeap.pop_back();

                _maxHeap.push_back(value);
                push_heap(_maxHeap.begin(), _maxHeap.end(), [](int left, int right){ return left >= right; });
            }
            else
            {
                _miniHeap.push_back(value);
                push_heap(_miniHeap.begin(), _miniHeap.end());
            }
        }
    }

    int get()
    {
        if (_miniHeap.size() == _maxHeap.size())
        {
            if (_miniHeap.empty())
            {
                throw runtime_error("Container is empty.");
            }

            return (_miniHeap.front() + _maxHeap.front()) / 2;
        }
        else 
        {
            return _maxHeap.front();
        }
    }

private:
    vector<int> _miniHeap;
    vector<int> _maxHeap;
};

void testGetMedian()
{
    //18.9 Numbers are randomly generated and passed to a method. Write a program to find
    //and maintain the median value as new values are generated
    array<int, 5> ints = {10, 20, 30, 5, 15};
    MedianValue mv;
    for_each(ints.begin(), ints.end(), [&mv](int value)
    {
        mv.add(value);
        cout << "Median value is " << mv.get() << " after inserting " << value << "." << endl;
    });
}

void testSearchString()
{
	//Given a string s and an array of smaller strings T, design a method to search s 
	//for each small string in T.
}

int _tmain(int argc, _TCHAR* argv[])
{
    testGetLongestWord();
    testGetMedian();
	testSearchString();
    cin.get();
	return 0;
}

